import java.util.Arrays;

public class Solution174 {
    public int calculateMinimumHP(int[][] dungeon) {
        int m = dungeon.length;
        int n = dungeon[0].length;
        int[] dp = new int[n];
        Arrays.fill(dp, Integer.MIN_VALUE);
        dp[n - 1] = Math.min(0, dungeon[m - 1][n - 1]);
        for (int i = m - 1; i >= 0; i--) {
            for (int j = n - 1; j >= 0; j--) {
                if (i != m - 1) {
                    dp[j] = Math.min(0, dungeon[i][j] + dp[j]);
                }
                if (j != n - 1) {
                    dp[j] = Math.max(dp[j], Math.min(0, dungeon[i][j] + dp[j + 1]));
                }
            }
        }
        return Math.max(1, -dp[0] + 1);
    }
}
